# JZ9 跳台阶扩展问题
#
# 描述
# 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。
# 求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。
# 示例1
# 输入：
# 3
# 返回值：
# 4

# 核心代码模式
# -*- coding:utf-8 -*-
# 试几个发现f(n)=f(n-1)+f(n-2)+...+f(0)
# 而f(n-1)=f(n-2)+...+f(0)
# 故 f(n)=2f(n-1)
# f(0)=f(1)=1
class Solution:
    def jumpFloorII(self, n):

        if n <= 1:
            return 1
        # 递归
        else:
            return 2 * self.jumpFloorII(n - 1)
        # 动态规划
#         a = 1
#         for i in range(2,n+1):
#             a *= 2
#         return a
